In this paper, we propose a new multi-armed bandit problem called theGambler's Ruin Bandit Problem (GRBP). In the GRBP, the learner proceeds in asequence of rounds, where each round is a Markov Decision Process (MDP) withtwo actions (arms): a continuation action that moves the learner randomly overthe state space around the current state; and a terminal action that moves thelearner directly into one of the two terminal states (goal and dead-end state).The current round ends when a terminal state is reached, and the learner incursa positive reward only when the goal state is reached. The objective of thelearner is to maximize its long-term reward (expected number of times the goalstate is reached), without having any prior knowledge on the state transitionprobabilities. We first prove a result on the form of the optimal policy forthe GRBP. Then, we define the regret of the learner with respect to anomnipotent oracle, which acts optimally in each round, and prove that itincreases logarithmically over rounds. We also identify a condition under whichthe learner's regret is bounded. A potential application of the GRBP is optimalmedical treatment assignment, in which the continuation action corresponds to aconservative treatment and the terminal action corresponds to a risky treatmentsuch as surgery.
展开▼
